package priorityqueue;

import java.util.Arrays;

public class Heap {
    //按照小堆的规则进行向下调整

    public static void shiftDown(int [] array,int size,int index){
        //要调整的父节点
        int parent = index;
        int child = 2 * parent + 1;

        //如果子节点下标超出数组范围,就说明子节点是不存在的
        //主循环结束,调整就完成了
        while(child < size){
            if(child + 1 < size&&array[child + 1] < array[child]){
                child = child + 1;
            }
            //通过该判定,可以找出左子树和右子树中更小的值,用child下标指向更小值
            //然后比较child和parent的大小
            if(array[parent] <= array[child]){
                break;
            }
            else{
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;
                parent = child;
                child = 2 * parent + 1;
            }
        }
    }

    //向上调整
    public static void shiftUp(int [] array,int index){
        int child = index;
        int parent = (child - 1) / 2;
        //当child为0时,就说明已经调整到了根节点,循环也就结束了
        while(child > 0){
            if(array[parent] > array[child]){
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;

                //更新child和parent的指向
                child = parent;
                parent = (child - 1)/2;
            }else{
                break;
            }
        }
    }

    public static void createHeap(int [] array){
        //找到最后一个非叶子节点
        //从后往前进行向下调整
        int lastLeaf = array.length - 1;
        int lastParent = (lastLeaf - 1) / 2;
        for(int i = lastParent;i >= 0;i--){
            shiftDown(array,array.length,i);
        }
    }
    public static void main(String[] args) {
        int []array = {1,2,3,6,5,7,8,9,10,0};
        createHeap(array);
        System.out.println(Arrays.toString(array));

    }
}
